USACO 2023 December Contest, Bronze

[USACO23DEC] Candy Cane Feast B

题目描述

Farmer John 的奶牛对甜食情有独钟，它们尤其喜欢吃糖果棒。FJ 共有 $N$ 头奶牛，每头奶牛都有一个特定的初始高度。他想要喂它们 $M$ 根糖果棒，每根糖果棒的高度也各不相同（$1\le N,M\le 2\cdot {10}^5$）。

FJ 计划按照输入给出的顺序，逐一喂给奶牛们糖果棒。然后，奶牛们会按照输入给出的顺序一个接一个地排队，走向糖果棒，每头奶牛最多吃到与它高度相同的部分（因为它们够不到更高的地方）。即使奶牛吃掉了糖果棒的底部，糖果棒也在最初悬挂的地方保持不动，并不会被降低到地面。如果糖果棒的底部已经高于某头奶牛的高度，那么这头奶牛在它的回合中可能什么也吃不到。每头奶牛轮流吃过后，它们的身高会增加它们吃掉的糖果棒的单位数量，然后农夫约翰挂上下一根糖果棒，奶牛们再次重复这个过程（第一头奶牛再次成为第一个开始吃下一根糖果棒的）。

输入格式

第一行包含 $N$ 和 $M$。

接下来的一行包含 $N$ 头奶牛的初始高度，每头奶牛的高度都在 $[1,{10}^9]$ 的范围内。

接下来的一行包含 $M$ 根糖果棒的长度，每根糖果棒的长度都在 $[1,{10}^9]$ 的范围内。

输出格式

输出 $N$ 行，表示每头奶牛最终的高度。

请注意，由于这个问题涉及的整数大小较大，可能需要使用 64 位整数数据类型（例如，在 C/C++ 中使用 long long 类型）。

输入输出样例 #1

输入 #1

3 2
3 2 5
6 1

输出 #1

7
2
7

说明/提示

样例解释 1

第一根糖果棒高度为 $6$ 单位。

• 第一头奶牛吃掉了第一根糖果棒直至高度 $3$ 的部分，之后第一根糖果棒剩余高度 $[3,6]$ 的部分。
• 第二头奶牛不够高，无法吃掉第一根糖果棒的任何剩余部分。
• 第三头奶牛额外吃掉了第一根糖果棒的两个单位。第一根糖果棒的剩余高度 $[5,6]$ 的部分未被吃掉。

接下来，每头奶牛根据它吃掉的数量增长，所以奶牛的高度变为 $[3+3,2+0,5+2]=[6,2,7]$。

第二根糖果棒高度为 $1$ 单位，被第一头奶牛全部吃掉。

测试点性质

• 测试点 $2-10$ 满足 $N,M\le {10}^3$。
• 测试点 $11-14$ 没有额外限制。

代码示例

#include"iostream"
#include"algorithm"
using namespace std;
long long a[200005]; 

int main(){
	int i,j,k,l,n,m,t;
	cin >> n >> m;
	for(i=0;i<n;i++){
		cin >> a[i];
	} 
	for(i=0;i<m;i++){
		cin >> k;
		l = 0;
		for(j=0;j<n;j++){
			if(a[j]>=k){
				a[j]+=k-l;
				break; 
			}
			if(a[j]>=l){
				t = a[j]; 
				a[j] += a[j]-l;
				l = t; 
			} 
		}
		
	}
	for(i=0;i<n;i++){
		cout<<a[i]<<endl;
	}	
		
	return 0;
}

[USACO23DEC] Cowntact Tracing 2 B

题目描述

Farmer John 有 $N$ 头奶牛排成一列（$1\le N\le 3\cdot {10}^5$）。不幸的是，有一种疾病正在传播。

最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它左右两边的奶牛（如果这些奶牛存在的话）。一旦奶牛被感染，她就会持续处于感染状态。

经过一些晚上，Farmer John 意识到情况已经失控，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。请找出最少有多少头奶牛最初可能感染了这种疾病。

输入格式

第一行为一个整数 $N$，即 Farmer John 拥有的奶牛数量。

接下来一行，包含长度为 $N$ 的由 $1$ 和 $0$ 组成的位串。其中 $1$ 表示一头被感染的奶牛，$0$ 表示一头在经过若干晚之后仍未被感染的奶牛。

输出格式

输出一个整数，表示最少有多少头奶牛可能最初感染了这种疾病。

输入输出样例 #1

输入 #1

5
11111

输出 #1

1

输入输出样例 #2

输入 #2

6
011101

输出 #2

4

说明/提示

样例解释 1

假设只有中间的奶牛最初被感染。那么，奶牛们将按以下顺序被感染：

• 第 $0$ 晚：$00100$（第三只奶牛一开始被感染）
• 第 $1$ 晚：$01110$（第二和第四只奶牛现在被感染了）
• 第 $2$ 晚：$11111$（第一和第五只奶牛现在被感染了）
• 第 $3$ 晚：$11111$（所有的奶牛都已经被感染了，没有新的奶牛被感染）
• ……

经过两个或更多的晚上，奶牛们的状态即与输入的状态相符。还有许多其他的初始状态和夜晚数量可能导致了输入的状态，例如：

• 第 $0$ 晚：$10001$
• 第 $1$ 晚：$11011$
• 第 $2$ 晚：$11111$

或者：

• 第 $0$ 晚：$01001$
• 第 $1$ 晚：$11111$

或者：

• 第 $0$ 晚：$01000$
• 第 $1$ 晚：$11100$
• 第 $2$ 晚：$11110$
• 第 $3$ 晚：$11111$

所有这些初始状态中至少有一头奶牛被感染。

样例解释 2

唯一可能导致这个最终状态的初始状态和夜晚数是：没有经过任何夜晚，输入中的四头感染的奶牛都是从最开始就感染了这种疾病。

测试点性质

• 测试点 $3-7$ 满足 $N\le 1000$。
• 测试点 $8-12$ 没有额外限制。

代码示例

#include <bits/stdc++.h>
using namespace std;

vector<int> v;

int main() {
    int n;
    string s;
    cin >> n >> s;

    int pre = 0, suf = n - 1, cnt = 0, minDay = n + 1;
    while (s[pre] == '1') pre++;
    while (suf > pre && s[suf] == '1') suf--;

    if (pre != 0) {
        v.push_back(pre);
        minDay = min(minDay, pre - 1);
    }
    if (suf != n - 1) {
        v.push_back(n - 1 - suf);
        minDay = min(minDay, n - 2 - suf);
    }

    for (int i = pre; i <= suf; i++) {
        if (s[i] == '1') cnt++;
        else if (s[i] == '0') {
            if (cnt > 0) {
                v.push_back(cnt);
                minDay = min(minDay, (cnt - 1) / 2);
            }
            cnt = 0;
        }
    }
    if (cnt > 0) {
        v.push_back(cnt);
        minDay = min(minDay, (cnt - 1) / 2);
    }

    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        int k = v[i] / (minDay * 2 + 1);
        if (v[i] % (minDay * 2 + 1)) k++;
        ans += k;
    }
    cout << ans;
    return 0;
}

[USACO23DEC] Farmer John Actually Farms B

题目描述

Farmer John 在他的农场上种植了 $N$（$1\le N\le 2\cdot {10}^5$） 株芦笋！然而，其中有一些植物存在基因差异，长得比其他植物快。第 $i$ 株植物的初始高度为 $h_i$ 英寸，之后每天，第 $i$ 株植物长高 $a_i$ 英寸。

FJ 更加钟爱其中的一些植物。他将给你一组由不同整数组成的数组 $t_1,\dots ,t_N$，这个数组包含 $0$ 到 $N-1$ 的全部整数。他希望恰好有 $t_i$ 株植物比第 $i$ 株植物高。找到最少要经过多少天，才能满足 FJ 的要求，或者报告这个要求是不可能满足的。

输入格式

每个测试点中包含多组测试数据。

第一行为一个整数 $T$，代表测试数据组数（$1\le T\le 10$）。

对于每一组测试数据，第一行一个整数 $N$（$1\le N\le 2\cdot {10}^5$），表示植物数量。

第二行包含 $N$ 个整数 $h_i$（$1\le h_i\le {10}^9$），表示第 $i$ 株植物的初始高度。

第三行包含 $N$ 个整数 $a_i$（$1\le a_i\le {10}^9$），表示第 $i$ 株植物每天增长的高度。

第四行包含 $N$ 个不同的整数 $t_i$，表示 FJ 给你的数组。

保证所有测试数据的 $N$ 的和不超过 $2\cdot {10}^5$。

输出格式

输出 $T$ 行，每行表示一组测试数据的答案。如果要求不可能满足，输出 $-1$。

请注意，由于这个问题涉及的整数大小较大，可能需要使用 64 位整数数据类型（例如，在 C/C++ 中使用 long long 类型）。

输入输出样例 #1

输入 #1

6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0

输出 #1

0
3
2
5
-1
-1

输入输出样例 #2

输入 #2

2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0

输出 #2

4
7

说明/提示

样例解释 1

在第一组样例中，有 $6$ 组测试数据。

在第一组测试数据中，只有一株植物，所以要求在第 $0$ 天就已经满足。

在第二组测试数据中，需要让第一株植物比第二株植物矮。第 $1$ 天后，它们的高度为 $15,13$；第 $2$ 天后，它们的高度均为 $23$；第 $3$ 天后，它们的高度为 $31,33$，这是满足要求的第一天。

第三组和第四组测试数据与第二组类似。

在第五组测试数据中，两株植物的初始高度均为 $7$ 英寸，且每天均增长 $8$ 英寸，所以它们的高度永远相同。因此，条件永远无法满足。

在第六组测试数据中，初始高度不满足要求且增长速度均相同，所以条件永远无法满足。

样例解释 2

在第二组样例中，有 $2$ 组测试数据。

在第一组测试数据中，第 $4$ 天后的最终高度为 $19,20,21,18,16$。

在第二组测试数据中，第 $7$ 天后的最终高度为 $25,17,19,35,36$。

测试点性质

• 测试点 $3$ 满足 $N\le 2$。
• 测试点 $4-5$ 满足 $N\le 50$，$a_i,h_i\le {10}^3$。
• 测试点 $6-8$ 满足 $N\le {10}^3$。
• 测试点 $9-13$ 没有额外限制。

代码示例

#include"iostream"
#include"algorithm"
using namespace std;

typedef long long ll;
const ll N = 2e5 + 10;
ll h[N], a[N], t[N], f[N];
ll T, n;

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> h[i];//初始高度
        for (int i = 1; i <= n; i++) cin >> a[i];//增量
        for (int i = 1; i <= n; i++) {
            cin >> t[i];
            f[t[i]] = i;//数组映射
        }
        ll ans = 0;
        for (int i = 1; i < n; i++) {
            if (a[f[i-1]] > a[f[i]] && h[f[i-1]] < h[f[i]]) {
                ll k = (h[f[i]] - h[f[i-1]] + 1) / (a[f[i - 1]] - a[f[i]]);
                if ((h[f[i]] - h[f[i-1]] + 1) % (a[f[i - 1]] - a[f[i]])) k++;
                ans = max(ans, k);
            }
        }
        //验证
        for (int i = 1; i <= n; i++) h[i] += ans * a[i];
        bool flag = 1;
        for (int i = 1; i < n; i++) {
            if (h[f[i-1]] <= h[f[i]]) flag = 0;
        }
        if (flag) cout << ans << endl;
        else cout << -1 << endl;
    }
    return 0;
}